package sliding_window;
import java.util.ArrayList;
import java.util.List;

// 找到字符串中所有字母异位词
public class Demo20250320 {
    public List<Integer> findAnagrams(String ss, String pp) {
        // 返回值
        List<Integer> ret = new ArrayList<>();
        // 将字符串转化为数组
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // 统计字符串 p 中每个字符出现的个数
        int[] hash1 = new int[26];
        for (char ch : p) {
            hash1[ch - 'a']++;
        }
        // 统计字符串 s 中每个字符出现的个数
        int[] hash2 = new int[26];
        // 计算 p 的长度
        int m = p.length;
        // 滑动窗口的逻辑
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            // 进窗口
            char in = s[right];
            // 有效字符进入 hash ， count++
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }
            // 判断，判断窗口的大小是否大于 p 的大小，大于则出窗口元素
            if (right - left + 1 > m) {
                int out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--; // 出的是有效元素 ，count--
                }
            }
            // 更新结果
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }

}
